#define _CRT_SECURE_NO_WARNINGS 1
class Solution {
public:
    vector<int> rightSideView(TreeNode* root)
    {
        queue<TreeNode*> q;
        if (root) q.push(root);
        vector<int> ret;

        while (q.size())
        {
            int sz = q.size();
            while (sz--)
            {
                TreeNode* front = q.front();
                q.pop();
                if (sz == 0) ret.push_back(front->val);
                if (front->left) q.push(front->left);
                if (front->right) q.push(front->right);
            }
        }

        return ret;
    }
};
class Solution
{
    int k;
    int ret = 0;
public:
    void dfs(TreeNode* root)
    {
        if (root == nullptr) return;
        if (k > 0) dfs(root->left);
        k--;
        if (k == 0)
        {
            ret = root->val;
            return;
        }
        if (k > 0) dfs(root->right);
    }
    int kthSmallest(TreeNode* root, int _k)
    {
        k = _k;
        dfs(root);
        return ret;
    }
};
class Solution
{
    long long prev = LLONG_MIN;
public:
    bool isValidBST(TreeNode* root)
    {
        if (root == nullptr) return true;
        bool left = isValidBST(root->left);
        if (!left) return false;
        if (root->val <= prev) return false;
        prev = root->val;
        bool right = isValidBST(root->right);
        if (!right) return false;
        return true;
    }
};
class Solution {
public:
    TreeNode* _sortedArrayToBST(vector<int>& nums, int begin, int end)
    {
        if (begin > end) return nullptr;
        int mid = begin + (end - begin) / 2;
        TreeNode* newnode = new TreeNode(nums[mid]);
        newnode->left = _sortedArrayToBST(nums, begin, mid - 1);
        newnode->right = _sortedArrayToBST(nums, mid + 1, end);

        return newnode;
    }
    TreeNode* sortedArrayToBST(vector<int>& nums)
    {
        return _sortedArrayToBST(nums, 0, nums.size() - 1);
    }
};
class Solution {
public:
    vector<vector<int>> levelOrder(TreeNode* root)
    {
        if (!root) return {};
        vector<vector<int>> ret;
        queue<TreeNode*> q;

        q.push(root);
        while (q.size())
        {
            int sz = q.size();
            vector<int> tmp;
            while (sz--)
            {
                TreeNode* top = q.front();
                q.pop();
                tmp.push_back(top->val);
                if (top->left) q.push(top->left);
                if (top->right) q.push(top->right);
            }
            ret.push_back(tmp);
        }
        return ret;
    }
};
class Solution
{
    int ret = 0;
public:
    int dfs(TreeNode* root)
    {
        if (root == nullptr) return 0;
        int leftheight = dfs(root->left);
        int rightheight = dfs(root->right);
        ret = max(ret, leftheight + rightheight);
        return max(leftheight, rightheight) + 1;
    }
    int diameterOfBinaryTree(TreeNode* root)
    {
        dfs(root);
        return ret;
    }
};
class Solution {
public:
    bool _isSymmetric(TreeNode* left, TreeNode* right)
    {
        if (!left && !right) return true;
        if ((left && !right) || (right && !left)) return false;
        if (left->val != right->val) return false;
        return _isSymmetric(left->left, right->right) && _isSymmetric(left->right, right->left);
    }
    bool isSymmetric(TreeNode* root)
    {
        if (root->left == nullptr && root->right == nullptr) return true;

        return _isSymmetric(root->left, root->right);
    }
};
class Solution {
public:
    TreeNode* invertTree(TreeNode* root)
    {
        if (root == nullptr) return nullptr;
        TreeNode* left = invertTree(root->left);
        TreeNode* right = invertTree(root->right);
        root->left = right;
        root->right = left;

        return root;
    }
};
class Solution {
public:
    int maxDepth(TreeNode* root)
    {
        if (root == nullptr) return 0;
        int left = maxDepth(root->left);
        int right = maxDepth(root->right);

        return max(left, right) + 1;
    }
};
class Solution {
public:
    vector<int> postorderTraversal(TreeNode* root)
    {
        stack<TreeNode*> st;
        TreeNode* cur = root;
        vector<int> ret;
        TreeNode* prev = nullptr;

        while (cur || st.size())
        {
            while (cur)
            {
                st.push(cur);
                cur = cur->left;
            }
            TreeNode* top = st.top();
            if (top->right != nullptr && prev != top->right)
            {
                cur = top->right;
            }
            else
            {
                ret.push_back(top->val);
                st.pop();
                prev = top;
            }
        }

        return ret;
    }
};
class Solution {
public:
    vector<int> inorderTraversal(TreeNode* root)
    {
        stack<TreeNode*> st;
        TreeNode* cur = root;
        vector<int> ret;

        while (cur || st.size())
        {
            while (cur)
            {
                st.push(cur);
                cur = cur->left;
            }

            TreeNode* top = st.top();
            st.pop();
            ret.push_back(top->val);
            if (top->right) cur = top->right;
        }

        return ret;
    }
};